import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

//给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
public class Solution {
    public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

    public TreeNode reConstructBinaryTree1 (int[] preOrder, int[] vinOrder) {
        int n = preOrder.length;
        int m = vinOrder.length;
        if (n == 0 || m == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.length; i++) {
            //在中序遍历中找第一个根节点
            if (preOrder[0] == vinOrder[i]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                        Arrays.copyOfRange(vinOrder, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                        Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
                break;
            }

        }
        return root;
    }


    //下面这个代码占用空间太多
    private HashMap<Integer,Integer> vinorderMap = new HashMap<>();
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        for(int i = 0; i < vinOrder.length; i++){
            vinorderMap.put(vinOrder[i],i);//根据值找对应的下标
        }
        return helper(preOrder,vinOrder,0,
                preOrder.length-1,0,vinOrder.length-1);
    }
    public TreeNode helper(int[] preOrder,int[] vinOrder, int preStart, int preEnd,
                           int vinStart, int vinEnd){
        if(preStart > preEnd || vinStart > vinEnd){
            return null;
        }
        int rootval = preOrder[preStart];//根节点是先序遍历的第一个节点
        TreeNode root = new TreeNode(rootval);
        int index = vinorderMap.get(rootval);//获取到中序遍历的下标
        int leftTreeSize = index - preStart;//根节点左子树节点数
        root.left = helper(preOrder,vinOrder,preStart+1,preStart + leftTreeSize,vinStart,index-1);
        root.right = helper(preOrder,vinOrder,preStart+leftTreeSize+1,preEnd,index+1,vinEnd);
        return root;
    }

    public static void main(String[] args) {
        int[] preOrder = {3,9,20,15,7};
        int[] vinOrder = {9,3,15,20,7};
        Solution solution = new Solution();
        TreeNode root = solution.reConstructBinaryTree(preOrder,vinOrder);
        System.out.println(root);
    }
}
